package arithmetic.LeetCode;

import java.util.HashMap;
import java.util.Map;
import java.util.Set;

import org.junit.jupiter.api.Test;

/**
 * @author jiangfeng 2019/7/29 16:17
 */
public class LongestSubStringNoRepeat {

    public static void main(String[] args) {

        Map m =null;
        Set s=null;
        //System.out.println( lengthOfLongestSubstring(""));
        String test1= " ";
        String test2= "abbac";
        String test3= "dvdf";
        System.out.println( lengthOfLongestSubstring(test2));
        //System.out.println( lengthOfLongestSubstring(test3));
        System.out.println(lengthOfLongestSubstring2(test2));

    }

    public static String lengthOfLongestSubstring2(String s) {
        if (s.length() < 2) {
            return s;
        }
        Map<Character, Integer> map = new HashMap();
        int start = 0, i = 0, maxLength = 0;
        String result = null;
        while (i < s.length()) {
            Integer c = map.get(s.charAt(i));
            if (c != null) {
                start = Math.max(start, c);
            }
            if (maxLength < i - start + 1) {
                maxLength = i - start + 1;
                result = s.substring(start, i+1);
            }
            map.put(s.charAt(i), i+1); // 关键点,应该指向该字符的下一个位置.
            i++;
        }
        return result;
    }

    public static int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> chars = new HashMap();
        int maxLength = 0;
        int start = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            Integer index = chars.get(c);
            if (null != index) {
                start = Math.max(index,start);// 防止重复
                //start = index;//
            }
            maxLength = Math.max(maxLength, i - start + 1);
            chars.put(c, i + 1);
        }
        return maxLength;
    }

   /* public static int lengthOfLongestSubstring(String s) {
        int n = s.length(), ans = 0;
        Map<Character, Integer> map = new HashMap<>(); // current index of character
        // try to extend the range [i, j]
        for (int j = 0, i = 0; j < n; j++) {
            if (map.containsKey(s.charAt(j))) {
                i = Math.max(map.get(s.charAt(j)), i);
            }
            ans = Math.max(ans, j - i + 1);
            map.put(s.charAt(j), j + 1);
        }
        return ans;
    }*/


    @Test
    public void test(){
        System.out.println(longestPalindrome("babad"));
    }



    public String longestPalindrome(String s) {
        // 中心扩散法.
        //char[] c = s.charArray();
        // 算上间隙.
        int len = s.length()*2-1;
        String res = "";

        for(int i = 0;i<len;i++){
            // 奇数就是缝隙.偶数就是数字
            // 0,0 0  1,0 ,1   2 1 1, 3 1,1
            int l = i/2;
            int r = i/2 + ((i%2==0)? 0:1);
            while(l>=0 && r< s.length() && s.charAt(l) == s.charAt(r) ){
                if( r-l+1>res.length()){
                    res = s.substring(l,r+1);
                }
                l--;
                r++;
            }

        }
        return res;

    }

}
